package leetcode.tree.binary;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树的节点
 *
 */
public class TreeNode {
    /**
     * 节点值
     */
    public int val;

    /**
     * 左节点
     */
    public TreeNode left;

    /**
     * 右节点
     */
    public TreeNode right;

    /**
     * 构造函数
     */
    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    /**
     * 使用数组创建二叉排序树(完全二叉树)
     *
     *
     * @param arr 数组
     * @return
     */
    public static TreeNode createTreeByArr(Integer[] arr) {
        if (arr == null || arr.length == 0) {
            return new TreeNode();
        }

        // 数组转化为节点列表
        List<TreeNode> nodes = new ArrayList<>(arr.length);
        for (Integer obj : arr) {
            TreeNode treeNode = new TreeNode();
            treeNode.val = obj;
            nodes.add(treeNode);
        }

        // 节点关联
        for (int i = 0; i < arr.length / 2 - 1; i++) {
            TreeNode node = nodes.get(i);
            node.left = nodes.get(i * 2 + 1);
            node.right = nodes.get(i * 2 + 2);
        }


        int lastPNodeIndex = arr.length / 2 - 1;
        TreeNode lastPNode = nodes.get(lastPNodeIndex);
        lastPNode.left = nodes.get(lastPNodeIndex * 2 + 1);
        if (arr.length % 2 != 0) {
            lastPNode.right = nodes.get(lastPNodeIndex * 2 + 2);
        }

        return nodes.get(0);
    }




}
